package leetcode.primary;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T47 {
    List<List<Integer>> ans;
    int len;
    public List<List<Integer>> permuteUnique(int[] nums) {
        len = nums.length;
        ans = new ArrayList<>();
        boolean[] used = new boolean[len];
        Arrays.sort(nums);
        DFS(0,new ArrayList<>(),nums,used);
        return ans;
    }

    public void DFS(int dfs_len, List<Integer> list,int[] nums,boolean[] used){
        if (dfs_len==len){
            List<Integer> temp = new ArrayList<>(list);
            ans.add(temp);
            return;
        }
        for (int j =0;j<len;j++){
            if (used[j] || j>0 && nums[j]==nums[j-1] && !used[j - 1]){
                continue;
            }
            list.add(nums[j]);
            used[j] = true;
            DFS(dfs_len+1,list,nums,used);
            list.remove(list.size()-1);
            used[j] = false;
        }
    }

    public static void main(String[] args) {
        T47 test = new T47();
        List<List<Integer>> list = test.permuteUnique(new int[]{1, 2, 3});
        for (List<Integer> integerList : list) {
            for (Integer i : integerList) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}
